package leetcode.dynamic_programming;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author mgl
 * @version 1.0
 * @description 三角形最小路径长度 leetcode120题
 * @date 2023/10/5 13:34
 */
public class MinimumTriangleTotal {

    public int minimumTotal(List<List<Integer>> triangle) {
        List<List<Integer>> arr = new ArrayList<>();
        arr.add(triangle.get(0));
        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> list = triangle.get(i);
            List<Integer> pre = arr.get(i - 1); //当前数组的上一列数组
            int preSize = pre.size();
            List<Integer> _lst = new ArrayList<>();

            for (int j = 0; j < list.size(); j++) {
                int left = j - 1;
                int right = j;

                if(left >= 0 && right < preSize) {
                    _lst.add(list.get(j) + Math.min(pre.get(left),pre.get(right)));
                }else if (left >= 0) {
                    _lst.add(list.get(j) + pre.get(left));
                } else if (right<preSize) {
                    _lst.add(list.get(j) + pre.get(right));
                }
            }
            arr.add(_lst);
        }
        List<Integer> res = arr.get(triangle.size()-1);
        int min  = res.get(0);
        for (int i = 1; i < res.size(); i++) {
            if (res.get(i) < min) {
                min = res.get(i);
            }
        }

        return min;
    }

    public static void main(String[] args) {
        List<List<Integer>> all = new ArrayList<>();
    }
}
